#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node* PtrToNode;

typedef int ElementType;

struct Node {
    ElementType Data;
    PtrToNode Next;
};

typedef PtrToNode Position;


typedef struct QNode* PtrToQNode;

struct QNode {
    Position Front, Rear;
    int Maxsize;
};

typedef PtrToQNode Queue;

Queue CreateQueue ( int Maxsize );

bool IsFull ( Queue Q );

bool AddQ ( Queue Q, ElementType X );

bool IsEmpty ( Queue Q );

ElementType DeleteQ ( Queue Q );

int main() {
    Queue Q = CreateQueue(10);
    int choice, X, result, i = 1;
    Position tmp;

    while(1) {
        printf("Queue\r\nPlease input\r\n1 Add\t2 Delete\n3 Print\t4 Exit\n");
        scanf("%d",&choice);
        switch (choice) {
        case 1:
            if ( IsFull(Q) ) {
                printf("Full\n");
                exit(-9);
            }
            printf("Please input\n");
            scanf("%d",&X);
            if ( AddQ(Q,X) ) printf("Success Add\n");
            break;
        case 2:
            if ( IsEmpty(Q) ) {
                printf("Empty\n");
                exit(-9);
            }
            result = DeleteQ(Q);
            printf("Delete\t%d\n",result);
            break;
        case 3:
            i = 1;
            tmp = Q->Front;
            printf("data\n");
            while (tmp) {
                printf("%d\t|\t%d\n",i++,tmp->Data);
                tmp = tmp->Next;
            }
            break;
        case 4:
            while(!IsEmpty(Q)) {
                DeleteQ(Q);
                printf("Delete Success\n");
            }
            printf("Free success!\n");
            exit(0);
            break;
        }
    }
    return 0;
}

Queue CreateQueue ( int Maxsize ) {
    Queue Q;
    Q = (Queue)malloc(sizeof(struct QNode));
    Q->Front = NULL;
    Q->Rear = NULL;
    Q->Maxsize = Maxsize;
    return Q;
}

bool IsFull ( Queue Q ) {
    int cnt = 0;
    Position PtrQ = Q->Front;
    while( PtrQ ) {
        cnt++;
        PtrQ = PtrQ->Next;
    }
    return ( cnt == Q->Maxsize );
}

bool AddQ ( Queue Q, ElementType X ) {
    if (IsFull(Q)) {
        printf("Full\n");
        return false;
    }
    if (IsEmpty(Q)) {
        Q->Front = (Position)malloc(sizeof(struct Node));
        Q->Front->Data = X;
        Q->Rear = Q->Front;
    } else {
        // Position tmp = Q->Rear->Next;
        Position tmp = (Position)malloc(sizeof(struct Node));
        tmp->Data = X;
        tmp->Next = NULL;
        Q->Rear->Next = tmp;
        Q->Rear = tmp;
    }
    return true;
}

bool IsEmpty ( Queue Q ) {
    return ( Q->Front == NULL );
}

ElementType DeleteQ ( Queue Q ) {
    Position FrontCell;
    ElementType FrontElem;

    if (IsEmpty(Q)) {
        printf("Empty\n");
        exit(-6);
    }

    FrontCell = Q->Front;
    if ( Q->Front == Q->Rear ) Q->Front = Q->Rear = NULL;
    else Q->Front = Q->Front->Next;
    FrontElem = FrontCell->Data;

    free(FrontCell);
    return FrontElem;
}